package merge_sort
import (
	"fmt"
	"math"
)

func merge(arr []int, lo int, mid int, hi int)  {
	len := len(arr)
	i := lo
	j := mid + 1
	aux := make([]int, len, len)
	copy(aux, arr)

	for k := lo; k <= hi; k++ {
		if i > mid {
			arr[k] = aux[j]
			j++
		} else if j > hi {
			arr[k] = aux[i]
			i++
		} else if aux[j] < aux[i] {
			arr[k] = aux[j]
			j++
		} else {
			arr[k] = aux[i]
			i++
		}
	}

}

func Sort(arr []int, lo int, hi int)  {
	if hi <= lo {
		return
	}
	mid := lo + (hi - lo) / 2

	Sort(arr, lo, mid)
	Sort(arr, mid+1, hi)
	fmt.Printf("merge(arr, %d, %d, %d)\n", lo, mid, hi)
	merge(arr, lo, mid, hi)
}

func Sort1(arr []int)  {
	N := len(arr)
	for sz := 1; sz < N; sz = sz+sz {
		for lo := 0; lo < N-sz; lo += sz+sz {
			merge(arr, lo, lo+sz-1, int(math.Min(float64(lo+sz+sz-1), float64(N-1))))
		}
	}
}
